package LinkedList;

import Node.ListNode;

public class IterationReverseBetweenList {
    public ListNode reverseBetween(ListNode head, int m, int n) {

        if (m == 1)
            return reverseN(head, n);
        // 找到第 m 个节点的前驱
        ListNode pre = head;
        for (int i = 1; i < m - 1 ; i++) {
            pre = pre.next;
        }
        // 从第 m 个节点开始，进行反转
        pre.next = reverseN(pre.next, n - m + 1);
        return head;
    }

    private ListNode reverseN(ListNode head, int n) {
        if (head == null || head.next == null)
            return head;
        ListNode cur, pre, next;
        pre = null;
        cur = head;
        next = head.next;
        while (n > 0) {
            cur.next = pre;
            pre = cur;
            cur = next;
            if (next != null) {
                next = next.next;
            }
            n--;
        }
        // 此时的 cur 是 第 n +　1 个节点，head是翻转后的尾节点
        head.next = cur;
        return head;
    }
}
